' Written by Craig'n'Dave
Module Module1
    ' Dijkstra's shortest path using a graph
    Function dijkstra(graph As Dictionary(Of String, Dictionary(Of String, Integer)), start As String, goal As String)
        'Initialise
        Dim infinity As Integer = 2147483647
        Dim distance As New Dictionary(Of String, Integer)
        Dim previous_vertex As New Dictionary(Of String, String)
        Dim shortest_path As New List(Of String)
        Dim shortest As String
        Dim cost As Integer

        ' Set the shortest distance from the start for all vertices to infinity
        For Each vertex In graph
            distance.Add(vertex.Key, infinity)
        Next
        ' Set the shortest distance from the start for the start vertex to 0
        distance(start) = 0

        ' Loop until all the vertices have been visited
        While graph.Count > 0
            ' Find the vertex with the shortest distance from the start
            shortest = Nothing
            For Each vertex In graph
                If shortest = Nothing Then
                    shortest = vertex.Key
                ElseIf distance(vertex.Key) < distance(shortest) Then
                    shortest = vertex.Key
                End If
            Next

            ' Calculate shortest distance for each edge
            For Each neighbour In graph(shortest)
                cost = neighbour.Value
                ' Update the shortest distance for the vertex if the new value is lower
                If graph.ContainsKey(neighbour.Key) And cost + distance(shortest) < distance(neighbour.Key) Then
                    distance(neighbour.Key) = cost + distance(shortest)
                    previous_vertex(neighbour.Key) = shortest
                End If
            Next

            ' The vertex has now been visited, remove it from the vertices to consider
            graph.Remove(shortest)
        End While

        ' Generate the shortest path
        ' Start from the goal, adding vertices to the front of the list
        Dim current_vertex As String = goal
        While current_vertex <> start
            shortest_path.Insert(0, current_vertex)
            current_vertex = previous_vertex(current_vertex)
        End While
        ' Add the start vertex
        shortest_path.Insert(0, start)

        ' Return the shortest shortest path
        Return shortest_path
    End Function

    Sub main()
        ' Main program starts here
        Dim graph = New Dictionary(Of String, Dictionary(Of String, Integer)) From {
        {"A", New Dictionary(Of String, Integer) From {{"B", 4}, {"C", 3}, {"D", 2}}},
        {"B", New Dictionary(Of String, Integer) From {{"A", 4}, {"E", 4}}},
        {"C", New Dictionary(Of String, Integer) From {{"A", 3}, {"D", 5}}},
        {"D", New Dictionary(Of String, Integer) From {{"A", 2}, {"C", 5}, {"F", 2}}},
        {"E", New Dictionary(Of String, Integer) From {{"B", 4}, {"G", 2}}},
        {"F", New Dictionary(Of String, Integer) From {{"D", 2}, {"G", 10}}},
        {"G", New Dictionary(Of String, Integer) From {{"E", 2}, {"F", 10}}}
        }

        Dim shortest_path As New List(Of String)
        shortest_path = dijkstra(graph, "A", "G")
        Console.WriteLine(String.Join(", ", shortest_path))
    End Sub
End Module
